import java.util.Arrays;

/**
 * 1034. 边框着色
 * https://leetcode-cn.com/problems/coloring-a-border/
 */
public class Solutions_1034 {
    public static void main(String[] args) {
//        int[][] grid = {{1, 1}, {1, 2}};
//        int r0 = 0, c0 = 0, color = 3;  // output: {{3, 3}, {3, 2}}

//        int[][] grid = {{1, 2, 2}, {2, 3, 2}};
//        int r0 = 0, c0 = 1, color = 3;  // output: {{1, 3, 3}, {2, 3, 3}}

//        int[][] grid = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
//        int r0 = 1, c0 = 1, color = 2;  // output: {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}

//        int[][] grid = {{1, 2, 1, 2, 1, 2}, {2, 2, 2, 2, 1, 2}, {1, 2, 2, 2, 1, 2}};
//        int r0 = 1, c0 = 3, color = 1;  // output: {{1, 1, 1, 1, 1, 2}, {1, 2, 1, 1, 1, 2}, {1, 1, 1, 1, 1, 2}}

        int[][] grid = {{2, 1, 3, 2, 1, 1, 2},
                        {1, 2, 3, 1, 2, 1, 2},
                        {1, 2, 1, 2, 2, 2, 2},
                        {2, 1, 2, 2, 2, 2, 2},
                        {2, 3, 3, 3, 2, 1, 2}};
        int r0 = 4, c0 = 4, color = 3;
        // output: {{2, 1, 3, 2, 1, 1, 3}, {1, 2, 3, 1, 3, 1, 3}, {1, 2, 1, 3, 2, 3, 3},
        //          {2, 1, 3, 3, 2, 3, 3}, {2, 3, 3, 3, 3, 1, 3}}

        int[][] result = colorBorder(grid, r0, c0, color);
        System.out.println(Arrays.deepToString(result));
    }

    private static int row = 0, col = 0, oriColor = -1;
    private static boolean[][] visited = null;

    /**
     * 1. 从 [r0, c0] 向四个方向进行搜索，若相邻方向上的值等于 grid[r0][c0]
     * 2. 是否需要改变颜色，还需要判断递归到的坐标，是否是在 grid 的边界上，即
     *          是否在最上一行：i = 0
     *          是否在最下一行：i = row - 1
     *          是否在最左一列：j = 0
     *          是否在最右一列：j = col - 1
     * 3. 若是不在 grid 的边界上，但是与其相邻的四个位置上，存在着不属性“连通分量”的坐标，那么，该坐标也需要进行着色
     */
    public static int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        row = grid.length;
        col = grid[0].length;
        oriColor = grid[r0][c0];
        visited = new boolean[row][col];
        dfs(grid, r0, c0);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] < 0) {
                    // dfs 完成后，grid 中数值为 -1 的坐标，即是需要着色的
                    grid[i][j] = color;
                }
            }
        }
        return grid;
    }

    public static void dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= row || j >= col) {
            // 索引越界
            return;
        }
        if (grid[i][j] != oriColor || visited[i][j]) {
            // 不属于“连通分量”，或者属于“连通分量”，但是该坐标已经访问过（即被标记为了负数）
            /**
             * 为什么需要加 visited？因为光一个 grid[i][j] != oriColor 的判断条件，无法判断重复访问
             *     int[][] grid = {{2, 1, 3, 2, 1, 1, 2},
             *                     {1, 2, 3, 1, 2, 1, 2},
             *                     {1, 2, 1, 2, 2, 2, 2},
             *                     {2, 1, 2, 2, 2, 2, 2},
             *                     {2, 3, 3, 3, 2, 1, 2}};
             *             int r0 = 4, c0 = 4, color = 3;  // output:
             * 如果未加 visited 判断，则 grid[r0][c0] 会重复访问，造成重复递归调用，导致栈溢出报错
             * 因为 grid[r0][c0] 的值一直会是 2，因为上、下、左、右的元素都是 2，那么 grid[r0][c0] 不会着色，所以值不会被标记为负数
             */
            return;
        }
        visited[i][j] = true;
        if (checkBorder(i, j) || checkFour(grid, i, j)) {
            // 当前坐标在边界上，
            // 或者不在边界上，但是四周存在不属于“连通分量”的元素时，也需要着色
            grid[i][j] = -1 * grid[i][j];
        }
        // 上
        dfs(grid, i - 1, j);
        // 下
        dfs(grid, i + 1, j);
        // 左
        dfs(grid, i, j - 1);
        // 右
        dfs(grid, i, j + 1);
    }

    /**
     * 检查 [i, j] 是否在矩阵的 grid 边界上
     */
    public static boolean checkBorder(int i, int j) {
        return i == 0 || j == 0 || i == row - 1 || j == col - 1;
    }

    /**
     * 检查 [i, j] 四周，是否存在不等于 oriColor 的，并且不等于 -oriColor 的
     * 因为 -oriColor 是手动标记为 -oriColor 的，原本数值为 oriColor
     */
    public static boolean checkFour(int[][] grid, int i, int j) {
        // 检查上边
        if (grid[i - 1][j] != oriColor && grid[i - 1][j] != -oriColor) {
            return true;
        }
        // 检查下边
        if (grid[i + 1][j] != oriColor && grid[i + 1][j] != -oriColor) {
            return true;
        }
        // 检查左边
        if (grid[i][j - 1] != oriColor && grid[i][j - 1] != -oriColor) {
            return true;
        }
        // 检查右边
        if (grid[i][j + 1] != oriColor && grid[i][j + 1] != -oriColor) {
            return true;
        }
        return false;
    }
}
